#include <bits/stdc++.h>
using namespace std;
using ll=long long;
// int main() 
// {
//     int n;cin>>n;
//     vector<ll> ret(n);
//     for(int i=0;i<n;i++)cin>>ret[i];
//     sort(ret.begin(),ret.end());
//     ll maxnum=ret.back();
//     bool is=true;
//     for(int i=0;i<ret.size()-1;i++)
//     {
//         if(maxnum%ret[i]==0)
//         {
//             ll x=maxnum/ret[i];
//             //判断是否是2的n次方的两种方法
//             // if(x-(x&-x)==0)is=true;
//             if(x&(x-1))
//             {
//                 is=false;
//                 break;
//             }
//         }
//         else 
//         {
//             is=false;
//             break;
//         }
//     }
//     if(!is)cout<<"NO"<<endl;
//     else cout<<"YES"<<endl;
//     return 0;
// }

// https://ac.nowcoder.com/acm/problem/16693

//0-1背包问题，选和不选，确定这两种状态下的状态转移方程即可
//需要注意会不会超过容量
//一般开二维数组即可
// int n,v;
// //dp[i][j]表示从前i个物品里选出体积不超过j的物品
// int main()
// {
//     cin>>v>>n;
//     vector<int> ret(n+1);
//     vector<vector<int>> dp(n+1,vector<int>(v+1,0));
//     for(int i=1;i<=n;i++)cin>>ret[i];
//     for(int i=1;i<=n;i++)
//     {
//         for(int j=1;j<=v;j++)
//         {
//             //需要分开计算，不能两个判断里都加max
//             if(j-ret[i]<0)dp[i][j]=dp[i-1][j];
//             else dp[i][j]=max(dp[i-1][j],ret[i]+dp[i-1][j-ret[i]]);
//         }
//     }
//     cout<<v-dp[n][v]<<endl;
//     return 0;
// }

//https://www.nowcoder.com/questionTerminal/b2b816e20e8343b49abbaf493886ce26
// int main()
// {
//     string s1,s2;
//     cin>>s1>>s2;
//     int len1=s1.size(),len2=s2.size();
//     int minl=INT_MAX;
//     for(int i=0;i<=len2-len1;i++)
//     {
//         int count=0;
//         for(int j=0;j<len1;j++)if(s2[j+i]==s1[j])count++;
//         minl=min(minl,len1-count);
//     }
//     cout<<minl<<endl;
//     return 0;
// }


//https://leetcode.cn/problems/3sum-closest/description/
//一会做掉
class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            sort(nums.begin(),nums.end());
            int ans,mindiff=INT_MAX;
            for(int i=0;i<=nums.size()-3;i++)
            {
                int left=i+1,right=nums.size()-1;
                while(left<right)
                {
                    int temp=nums[i]+nums[left]+nums[right];
                    if(temp==target)return target;
                    if(temp>target)
                    {
                        if(temp-target<mindiff)
                        {
                            mindiff=temp-target;
                            ans=temp;
                        }
                        right--;
                    }
                    else
                    {
                        if(target-temp<mindiff)
                        {
                            mindiff=target-temp;
                            ans=temp;
                        }
                        left++;
                    }
                }
            }
            return ans;
        }
    };